#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// 迪杰斯特拉算法其实就比较像我的思路了, 每次只更新指定节点的长度
constexpr int MAXV = 100, MAXE = 100, INF = 1 << 30;
int cost[MAXV][MAXV]; // 表示权值e(u, v)
int d[MAXV]; // 从顶点V出发的最短距离
bool used[MAXV]; // 节点是否已经被使用
int V;

void dijkstra(int s) {
    for (int i = 0; i < V; i++) d[i] = INF;
    d[s] = 0; used[s] = true;
    while (true) {
        for (int i = 0; i < V; i++) {
            d[i] = min(d[i], d[s] + cost[s][i]); // 计算从这个点出发的最小值
        }
        int minimum = INF;
        bool next = false;
        for (int i = 0; i < V; i++) {
            if (!used[i] && d[i] < minimum) {
                s = i; minimum = d[i];
                next = true;
            }
        }
        if (!next) break;
    }
}

// 标准的答案
/**
 * 它的思想在于说每次找到没有使用, 并且距离最小的点, 然后从这个点出发
 * 我的想法是每次首先更新所有的点, 然后从这些点中找到没有被使用的最小点
 * 相当于我们俩的先后顺序不一样
 */
void dijkstra_standard(int s) {
    fill(d, d + V, INF);
    fill(used, used + V, false);
    d[s] = 0;
    while (true) {
        int v = -1; // 这一步是选点
        for (int i = 0; i < V; i++)
            if (!used[i] && (v = -1 || d[i] < d[v])) v = i; // 这个代码就写的很简洁好看
        if (v == -1) break;
        used[v] = true;
        for (int i = 0; i < V; i++)
            d[i] = min(d[i], d[v] + cost[v][i]);
    }
}
